package main

import "fmt"

/*
顿悟！
假设0-i的前缀和累加为x，也就是说前缀和数组第i位上为x
求以i为结尾的子数组的有多少个在[upper,lower]范围上
等同于去求前缀和数组中i之前的前缀和有多少在[x-up,x-l]上
例子:假设第2位上的前缀和数组符合[x-up,x-l]上设x为100，up为20，l为0
[80,100]，如果第二位的前缀和数组在80,100内就代表了从第三位起到i位置的累加和在[0,20]的范围上
所以这个子数组符合要求，这个第二位的前缀和的值不受任何其他因素影响，当然i位置的前缀和的值也不受其他任何因素影响
如果他们排序完打乱了顺序只要符合前一个的前缀和的值在后一个前缀和的的值-up，-l]范围内就可以了
所以随便他们如何排序只要保证比较的双方大范围内不乱小范围的排序无关系
*/
func main() {
	arr := []int{3, 2, 4, 9}

	sum := RangeSum(arr, -10, 20)
	fmt.Println(sum)

}

func RangeSum(nums []int, lower, upper int) int {
	if nums == nil && len(nums) == 0 {
		return 0
	}
	sum := make([]int, len(nums))
	sum[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		sum[i] += nums[i] + sum[i-1]
	}

	return count(sum, 0, len(nums)-1, lower, upper)
}

// 求sum从l到r中 有多少个子数组累加和在lower 和upper范围内
func count(sum []int, L, R, lower, upper int) int {
	if L == R { //当l==r相等时，判断当前前缀和的值是否相等，只要相等0-L的子数组就符合要求，这样子就相当于判断了0到所有位置的子数组符不符合要求所以merge里面判断前缀和不用从0开始
		if sum[L] >= lower && sum[L] <= upper {
			return 1
		} else {
			return 0
		}
	}
	M := (L + R) / 2
	return count(sum, L, M, lower, upper) + count(sum, M+1, R, lower, upper) + merge4(sum, L, M, R, lower, upper)
}

func merge4(sum []int, l int, m int, r int, lower int, upper int) int {

	ans := 0
	windowL := l
	windowR := l
	for i := m + 1; i <= r; i++ {
		min := sum[i] - upper
		max := sum[i] - lower
		for windowR <= m && sum[windowR] <= max {
			windowR++
		}

		for windowL <= m && sum[windowL] < min {
			windowL++
		}

		ans += windowR - windowL

	}
	help := make([]int, r-l+1)

	p1 := l
	p2 := m + 1
	i := 0

	for p1 <= m && p2 <= r {

		if sum[p1] < sum[p2] {
			help[i] = sum[p1]
			p1++
			i++
		} else if sum[p2] < sum[p1] {
			help[i] = sum[p2]

			p2++
			i++

		} else {
			help[i] = sum[p1]
			p1++
			i++
		}
	}

	if p2 > r {

		for p1 <= m {
			help[i] = sum[p1]
			p1++
			i++
		}
	}

	if p1 > m {

		for p2 <= r {
			help[i] = sum[p2]
			p2++
			i++
		}
	}

	for i, v := range help {
		sum[l+i] = v

	}
	return ans

}
